#include <iostream>

using namespace std;

// 非递归二分查找
// 1.设置first和last指针，分别指向数组的第一个和最后一个元素
// 2.当first<=last时，进行循环
// 3.计算mid=(first+last)/2，如果mid对应的值等于x，则返回mid
// 4.如果mid对应的值大于x，则last=mid-1
// 5.如果mid对应的值小于x，则first=mid+1
// 6.如果循环结束，还没有找到x，则返回-1
int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}


int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int index = binarySearch(arr, 0, 9, 10);
    cout << "index=" << index << endl;
    index = binarySearch(arr, 0, 9, 11);
    cout << "index=" << index << endl;
    index = binarySearch(arr, 0, 9, 5);
    cout << "index=" << index << endl;
    return 0;
}